#include <iostream>
#include <cstdlib>
using namespace std;

void Swap(int * a, int * b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int Partition(int data[], int length, int start, int end)
{
    if (data == NULL || length <= 0 || start < 0 || end >= length)
    {
        cout << "invalid input" << endl;
        exit(0);
    }
    int index = (start + end) / 2;
    Swap(&data[index], &data[end]);

    int small = start - 1;
    for(index = start; index < end; ++index)
    {
        if(data[index] < data[end])
        {
            ++ small;
            if(small != index)
                Swap(&data[small], &data[index]);
        }
    }
    ++small;
    Swap(&data[small], &data[end]);

    return small;
}

int Search(int data[], int length, int start, int end, int Kth)
{
    int m = Partition(data, length, start, end);
    // cout << m << endl;
    if (Kth == m - start + 1)
        return data[m];
    else if (Kth < m - start + 1)
        return Search(data, length, start, m - 1, Kth);
    else
        return Search(data, length, m + 1, end, Kth - (m - start + 1));  // Kth - (m - start + 1)
}
// 针对数据量较小的可以采用该方法，如果数据量很大，需要采用最小/最大堆动态调整，只保留前Kth个最大的数或最小的数。
int main(int argc, char * argv[])
{
    int data[] = {2, 3, 4, 4, 6, 7, 8};
    int length = sizeof(data) / sizeof(int);
    int Kth = 5;
    if (Kth > length)
    {
        cout << "Kth must be not less than length" << endl;
        return 0;
    }
    int KthValue = Search(data, length, 0, length-1, 7);
    cout << KthValue << endl;
    return 0;
}
